#include "BinarTree.h"

BinarTree::BinarTree()
{
    root = nullptr;
}

BinarTree::~BinarTree()
{
    Free(root);
}

void BinarTree::Insert(const ElementType& element)
{
    root = InsertNode(root,element);
}

BinarTree::ElementType* BinarTree::Find(const ElementType &element)
{
    return FindNode(root,element);
}

void BinarTree::Remove(const ElementType &element)
{

}

void BinarTree::show()
{
    std::cout<<"前：";
    PrevSort(root);
    std::cout<<std::endl;

    std::cout<<"中：";
    MidSort(root);
    std::cout<<std::endl;

    std::cout<<"后：";
    PostSort(root);
    std::cout<<std::endl;

    std::cout<<"层：";
    LinkQueue q;
    q.Push(root);
    while(!q.IsEmpty())
    {
        TreeNode* node = (TreeNode*)*q.GetFront();
        std::cout<<node->data<<" ";
        q.Pop();
        if(node->left)
            q.Push(node->left);
        if(node->right)
            q.Push(node->right );
    }
    std::cout<<std::endl;
}

BinarTree::TreeNode *BinarTree::InsertNode(TreeNode *node, const ElementType &element)
{
    if(node == nullptr)
        return node = new TreeNode(element);
    if(node->data > element)
    {
        node->left = InsertNode(node->left,element);
    }
    else if(node->data < element)
    {
        node->right = InsertNode(node->right,element);
    }
    else
        return node;
    return node;


}

void BinarTree::PrevSort(TreeNode *node)
{
    if(node == nullptr)
        return;
    std::cout<<node->data<<" ";
    PrevSort(node->left);
    PrevSort(node->right);
}

void BinarTree::MidSort(TreeNode *node)
{
    if(node == nullptr)
        return;
    
    MidSort(node->left);
    std::cout<<node->data<<" ";
    MidSort(node->right);
}

void BinarTree::PostSort(TreeNode *node)
{
    if(node == nullptr)
        return;
    
    PostSort(node->left);
    PostSort(node->right);
    std::cout<<node->data<<" ";
}

void BinarTree::Free(TreeNode *node)
{
    if(node == nullptr)
        return;
    Free(node->left);
    Free(node->right);
    delete node;
}

BinarTree::ElementType *BinarTree::FindNode(TreeNode *node, const ElementType &element)
{
    if(node == nullptr)
        return nullptr;
    if(node->data == element)
        return  &node->data;
    else if(node->data > element)
        return FindNode(node->left,element);
    else
        return FindNode(node->right,element);
}

BinarTree::TreeNode *BinarTree::RemoveNode(TreeNode *node, const ElementType &element)
{
    if(node == nullptr)
        return nullptr;
    if(node->data > element)
        node->left = RemoveNode(node->left,element);
    else if(node->data < element)
        node->right = RemoveNode(node->right,element);
    else
    {
        if(node->left == nullptr && node->right == nullptr)
        {
            delete node;
            return nullptr;
        }
        else if(node->left && node->right)
        {
            TreeNode *Minright = GetMinNode(node->right);
            node->data = Minright->data;
            node->right = RemoveNode(node->right,Minright->data);
           
        }
        else
        {
            TreeNode* child = node->left ? node->left : node->right;
            delete node;
            return child;
        }
    }
    return node;
}

BinarTree::TreeNode *BinarTree::GetMinNode(TreeNode *node)
{
    TreeNode *MinNode = node;
    while(!MinNode->left)
        MinNode = MinNode->left;
    return MinNode;
    
}
